24 game [DFS]

Time: O(1); Space: O(1); hard

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Notes:

  • The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.

  • Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.

  • You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Example 1:

Input: nums = [4, 1, 8, 7]

Output: True

Explanation:

  • (8 - 4) * (7 - 1) = 24

  • 8 * (7 - 4）* 1 = 24

Example 2:

Input: nums = [1, 2, 1, 2]

Output: False

Example 3:

Input：nums = [3, 3, 8, 8]

Output：True

Explanation:

  • 8 / ( 3 - 8 / 3) = 24

[1]:

from operator import add, sub, mul, truediv
from fractions import Fraction

class Solution1(object):
    """
    Time: O(N^3*4^N)=O(1),N=4
    Space: O(N^2)=O(1)
    """
    def judgePoint24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) == 1:
            return abs(nums[0]-24) < 1e-6

        ops = [add, sub, mul, truediv]

        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                next_nums = [nums[k] for k in range(len(nums)) if i != k != j]
                for op in ops:
                    if ((op is add or op is mul) and j > i) or \
                        (op == truediv and nums[j] == 0):
                        continue
                    next_nums.append(op(nums[i], nums[j]))
                    if self.judgePoint24(next_nums):
                        return True
                    next_nums.pop()
        return False

[7]:

s = Solution1()
nums = [4, 1, 8, 7]
assert s.judgePoint24(nums) == True
nums = [1, 2, 1, 2]
assert s.judgePoint24(nums) == False
nums = [3, 3, 8, 8]
assert s.judgePoint24(nums) == True

[8]:

from operator import add, sub, mul, truediv

class Solution2(object):
    def judgePoint24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        def dfs(nums):
            if len(nums) == 1:
                return nums[0] == 24
            ops = [add, sub, mul, truediv]

            for i in range(len(nums)):
                for j in range(len(nums)):
                    if i == j:
                        continue
                    next_nums = [nums[k] for k in range(len(nums))
                                 if i != k != j]
                    for op in ops:
                        if ((op is add or op is mul) and j > i) or \
                            (op == truediv and nums[j] == 0):
                            continue
                        next_nums.append(op(nums[i], nums[j]))
                        if dfs(next_nums):
                            return True
                        next_nums.pop()
            return False

        return dfs(list(map(Fraction, nums)))

[9]:

s = Solution2()
nums = [4, 1, 8, 7]
assert s.judgePoint24(nums) == True
nums = [1, 2, 1, 2]
assert s.judgePoint24(nums) == False
nums = [3, 3, 8, 8]
assert s.judgePoint24(nums) == True